package fun.ipconfig.rb;

import fun.ipconfig.DataCompare;

/**
 * @param <T>
 * @author gtinlian
 * @description: 红黑树管理类
 * <p>
 * 性质1：每个节点要么是黑色，要么是红色。
 * 性质2：根节点是黑色。
 * 性质3：每个叶子节点（NIL）是黑色。
 * 性质4：每个红色节点的两个子节点一定都是黑色。 不能有两个红色节点相连。
 * 性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。
 */
public class RbTree<T extends DataCompare> {
    RbTreeNode<T> root;

    /**
     * 插入节点，自平衡节点， 节点DataIndex 相同时覆盖
     *
     * @param node
     */
    public void insert(RbTreeNode<T> node) {
        node = findInsert(node);
        /* 破坏了性质4 */
        if (node != null && node.parentNotNull() && node.parent.parentNotNull() && !node.parent.isBlock()) {
            while(true) {
                if (! node.parentNotNull() || node.parent.isBlock() || node.reset(this)) {
                    return;
                }
                node = node.parent.parent;
            }
        }
    }

    /**
     * 查找并插入节点
     *
     * @param node 接地但
     * @return 返回null表示平衡 返回node 则需要判断是否符合红黑树规则
     */
    RbTreeNode<T> findInsert(RbTreeNode<T> node) {
        /* 根节点判断 */
        if (root == null) {
            root = node;
            root.color = RbTreeColor.block;
            return null;
        }
        /* 插入逻辑 */
        RbTreeNode<T> nextNode = root;
        while (true) {
            switch (node.getNext(nextNode)) {
                
                /* 索引值相同替换内容 */
                case EQ: {
                    nextNode.data = node.data;
                    return null;
                }
                
                /* 插入节点大于当前节点 */
                case GT: {
                    if (nextNode.rightIsNull()) {
                        nextNode.setRight(node);
                        node.setParent(nextNode);
                        return node;
                    } else {
                        nextNode = nextNode.right;
                        break;
                    }
                }
                
                /* 插入节点小于当前节点 */
                case LT: {
                    if (nextNode.leftIsNull()) {
                        node.setParent(nextNode);
                        nextNode.setLeft(node);
                        return node;
                    } else {
                        nextNode = nextNode.left;
                        break;
                    }
                }
                default:
                    break;
            }
        }
    }

    public RbTreeNode<T> find(RbTreeNode<T> node) {
        RbTreeNode<T> next = root;
        while (next != null) {
            if (next.data.index() == node.data.index()) {
                return next;
            } else {
                next = next.data.index() > node.data.index() ? next.left : next.right;
            }
        } 
        return null;
    }
    
    @Override
    public String toString() {
        return root.toString();
    }
}
